package datastructure.tree;

import utils.printer.BinaryTreeInfo;
import lombok.Data;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description: 二叉树
 * @Author Ammar
 * @Create 2023/4/4 23:26
 */
@Data
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected TreeNode<E> root;

    // 元素数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空所有元素
    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public Object root() {
        return root;
    }

    protected void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    public void add(List<E> vals) {
        for (E val : vals) {
            add(val);
        }
    }

    public void add(E val) {
        // 添加第一个节点
        if (root == null) {
            root = new TreeNode<>(val, null);
            size++;
            afterAdd(root);
            return;
        }
        // 层序遍历添加节点
        Queue<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<E> node = queue.poll();
            if (node.left == null) {
                node.left = new TreeNode<>(val, node);
                size++;
                afterAdd(node.left);
                return;
            }
            if (node.right == null) {
                node.right = new TreeNode<>(val, node);
                size++;
                afterAdd(node.right);
                return;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }

    protected TreeNode<E> createNode(E val, TreeNode<E> parent) {
        return new TreeNode<>(val, parent);
    }

    // 添加节点之后
    protected void afterAdd(TreeNode<E> node) {
    }

    public void preorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root, visitor);
    }

    /**
     * 递归前序遍历
     * @param node
     */
    private void preorderTraversal(TreeNode<E> node, Visitor<E> visitor) {
        if (root == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.val);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    /**
     * 中序遍历
     * @param node
     */
    private void inorderTraversal(TreeNode<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.val);
        inorderTraversal(node.right, visitor);
    }

    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root, visitor);
    }

    /**
     * 后序遍历
     * @param node
     */
    private void postorderTraversal(TreeNode<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.val);
    }

    public void levelOrderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        levelOrderTraversal(root, visitor);
    }

    /**
     * 层序遍历
     * @param node
     */
    private void levelOrderTraversal(TreeNode<E> node, Visitor<E> visitor) {
        if (node == null) return;
        Queue<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            TreeNode<E> parentNode = queue.poll();
            if (visitor.visit(parentNode.val)) return;
            if (parentNode.left != null) {
                queue.offer(parentNode.left);
            }
            if (parentNode.right != null) {
                queue.offer(parentNode.right);
            }
        }
    }

    /**
     * 计算二叉树的高度
     * @return
     */
    public int height() {
        if (root == null) return 0;
        int height = 0;
        int levelSize = 1;
        Queue<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<E> parentNode = queue.poll();
            levelSize--;
            if (parentNode.left != null) {
                queue.offer(parentNode.left);
            }
            if (parentNode.right != null) {
                queue.offer(parentNode.right);
            }
            if (levelSize == 0) {
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 是否为完全二叉树
     * @return
     */
    public boolean isComplete() {
        if (root == null) return false;
        Queue<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            TreeNode<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
//            if (node.hasTwoChildren()) {
//                queue.offer(node.left);
//                queue.offer(node.right);
//            } else if (node.left == null && node.right != null) {
//                return false;
//            } else if (node.left != null && node.right == null) {
//                queue.offer(node.left);
//                leaf = true;
//            } else {
//                leaf = true;
//            }
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

    /**
     * 获取任意节点的前驱节点
     * @param node
     * @return
     */
    public TreeNode predecessor(TreeNode node) {
        if (node == null) return null;
        TreeNode p = node.left;
        // 如果左子树不为空，前驱节点就是左子树中最右边的节点
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 如果左子树为空，前驱节点就是父节点或者 node = node.parent.right 的时候的 parent
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        // 要么 node.parent == null，要么 node == node.parent.right
        return node.parent;
    }

    public TreeNode successor(TreeNode node) {
        if (node == null) return null;
        TreeNode p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }

    @Override
    public Object left(Object node) {
        return ((TreeNode<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((TreeNode<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return node.toString();
    }


    public static abstract class Visitor<E> {
        boolean stop;

        public abstract boolean visit(E element);
    }
}
